

# 51. N皇后


def solveNQueens(n):
    """
    :type n: int
    :rtype: List[List[str]]
    """
    result = []
    temp = []

    def judge(temp, heng, zong):

        # 00 12
        for i in temp:
            heng1 = heng
            heng2 = heng
            heng3 = heng
            heng4 = heng
            zong1 = zong
            zong2 = zong
            zong3 = zong
            zong4 = zong
            if i[0] == heng or i[1] == zong:
                return False
            while heng1 >= 0 and heng1 < n - 1 and zong1 >= 0 and zong1 < n - 1:
                heng1 = heng1 + 1
                zong1 = zong1 + 1
                if i[0] == heng1 and i[1] == zong1:
                    return False
            while heng2 > 0 and heng2 <= n - 1 and zong2 >= 0 and zong2 < n - 1:
                heng2 = heng2 - 1
                zong2 = zong2 + 1
                if i[0] == heng2 and i[1] == zong2:
                    return False
            while heng3 >= 0 and heng3 < n - 1 and zong3 > 0 and zong3 <= n - 1:
                heng3 = heng3 + 1
                zong3 = zong3 - 1
                if i[0] == heng3 and i[1] == zong3:
                    return False
            while heng4 > 0 and heng4 <= n - 1 and zong4 > 0 and zong4 <= n - 1:
                heng4 = heng4 - 1
                zong4 = zong4 - 1
                if i[0] == heng4 and i[1] == zong4:
                    return False
        return True


    def backtrack(tempHeng,tempZong):
        if len(temp) == n and temp not in result:
            result.append(temp[:])
        for i in tempHeng:
            for j in tempZong:
                if judge(temp, i, j):
                    temp.append([i, j])
                    tempHeng.remove(i)
                    tempZong.remove(j)
                    backtrack(tempHeng,tempZong)
                    temp.pop()
                    tempHeng.append(i)
                    tempZong.append(j)
    tempHeng = []
    tempZong = []
    for i in range(0,n):
        tempHeng.append(i)
    for i in range(0,n):
        tempZong.append(i)
    backtrack(tempHeng,tempZong)
    results = []
    if n==1:
        return 'Q'
    for i in result:
        temp = ['']*n
        for j in i:
            for q in range(0,n):
                if j[1]==q:
                    str = ''
                    str = str + "."*q
                    str = str + 'Q'
                    str = str + "."*(n-q-1)
                    temp[j[0]] = str
        if temp not in results:
            results.append(temp)
    return results


if __name__ == "__main__":
    result =  solveNQueens(7)
    print(result)